"""
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。



def dfs(grid, i, j, current_weight, result):
    n = len(grid[0])
    m = len(grid)
    current_weight += grid[i][j]
    if i == m - 1 and j != n - 1:
        for q in range(j + 1, n):
            current_weight += grid[i][q]
        result.append(current_weight)
        current_weight = 0
        return
    elif j == n - 1 and i != m - 1:
        for p in range(i + 1, m):
            current_weight += grid[p][j]
        result.append(current_weight)
        current_weight = 0
        return
    elif i == m - 1 and j == n - 1:
        result.append(current_weight)
        current_weight = 0
        return
    # right
    for k in range(i + 1, m):
        dfs(grid=grid, i=i, j=j + 1, current_weight=current_weight, result=result)
    # down
    for q in range(j + 1, n):
        dfs(grid=grid, i=i + 1, j=j, current_weight=current_weight, result=result)
    current_weight -= grid[i][j]
class Solution:
    def minPathSum(self, grid):
        current_weight = 0
        result = []
        n = len(grid[0])
        m = len(grid)
        dfs(grid=grid, i=0, j=0, current_weight=current_weight, result=result)
        return min(result)
"""

class Solution:
    def minPathSum(self, grid: [[int]]) -> int:
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if i == j == 0: continue
                elif i == 0:  grid[i][j] = grid[i][j - 1] + grid[i][j]
                elif j == 0:  grid[i][j] = grid[i - 1][j] + grid[i][j]
                else: grid[i][j] = min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j]
        return grid[-1][-1]